package Algorithm.BinaryResearch;

import java.util.HashMap;
import java.util.Map;
//https://leetcode-cn.com/problems/online-election/
//911. 在线选举
public class Leetcode911 {
    class TopVotedCandidate {
        Map<Integer, Integer> map;
        int[] result;
        int len;
        int[] temp;

        public TopVotedCandidate(int[] persons, int[] times) {
            len = times.length;
            temp = times;
            map = new HashMap();
            result = new int[times.length];
            int max = 0;
            int maxInedex = 0;

            for(int i=0;i<times.length;i++){
                //计算选票
                int old = map.getOrDefault(persons[i],0);
                old = old + 1;
                if(old >= max){
                    max = old;
                    maxInedex = persons[i];
                }

                //记录time[i]时刻领先的候选人编号
                result[i] = maxInedex;
                map.put(persons[i], old);
            }

        }

//        public int q(int t) {
//            //二分查找
//            int l = 0;
//            int r = len-1;
//            while(l<=r){
//                int mid = (l+r)/2;
//                if(t == temp[mid]){
//                    return result[mid];
//                }else if(t<temp[mid]){
//                    r = mid - 1;
//                }else{
//                    l = mid + 1;
//                }
//            }
//            return result[l-1];
//        }

        public int q(int t) {
            //二分查找
            int l = 0;
            int r = len - 1;
            while(l<r){
                // 因为在本题，mid 也在正确的取值范围内，所以需要 l = mid，
                // 如果不 +1 当 l = 1,r = 2时，mid=1，会陷入死循环，要注意这个问题
                int mid = l+(r-l+1)/2;
                if(t == temp[mid]){
                    return result[mid];
                }else if(t<temp[mid]){
                    r = mid - 1;
                }else{
                    l = mid ;
                }
            }
            return result[l];
        }
    }

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */
}
